package com.ds.bintree.LeetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: TODO
 * @date 2022/9/17 1:18
 */
public class Num106_InAndPostBuildTree {
    Map<Integer,Integer> map = new HashMap<>(); //根据后续遍历的值从中序遍历中找索引
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length==0){
            return null;
        }
        for (int i = 0; i <inorder.length ; i++) {
            map.put(inorder[i],i);
        }
        return mybuild(postorder,0,postorder.length-1,0,inorder.length-1);
    }

    public TreeNode mybuild(int[] postorder,int postleft,int postright,int inleft,int inright) {
        if (postleft-postright>0 || inleft-inright>0){
            return null;
        }
        int pivot = map.get(postorder[postright]);
        TreeNode root = new TreeNode(postorder[postright]);
        root.left = mybuild(postorder,postleft,pivot-1-inleft+postleft,inleft,pivot-1);
        root.right = mybuild(postorder,pivot-inleft+postleft,postright-1,pivot+1,inright);
        return root;
    }
}
